namespace _6.图;

public sealed class 邻接矩阵表示法
{
	//邻接矩阵表示图
	public struct AMGraph
	{
		//顶点表
		char[] Vexs;
		//邻接矩阵
		int[][] Arcs;
		//图的当前的点数目
		int VexCount;
		//图当前边的数目
		int ArcCount;

		public AMGraph(char[] vexs, int[][] arcs)
		{
			Vexs = vexs;
			Arcs = arcs;
			VexCount = vexs.Length;
			CalcArcCount();
		}

		public void CalcArcCount()
		{
			for (int i = 0; i < Arcs.Length; i++)
				for (int j = 0; j < Arcs[i].Length; j++)
					if (Arcs[i][j] != int.MaxValue)
						ArcCount++;
		}

		//根据顶点查找在顶点表的下标
		public int LocateVex(char c)
		{
			for (int i = 0; i < Vexs.Length; i++)
				if (Vexs[i] == c)
					return i;
			return -1;
		}

		//非递归方式
		public void DFS(int start)
		{
			if (start < 0 || start > VexCount - 1)
			{
				throw new InvalidOperationException($"给定位置不合法");
			}

			//辅助数组
			var visited = new bool[Vexs.Length];
			//辅助栈
			var stack = new Stack<int>(VexCount);

			//访问第一个位置
			Console.WriteLine(Vexs[start]);
			//记录位置并入栈
			visited[start] = true;
			stack.Push(start);

			int[] curCol = Arcs[start];
			for (int i = 0; i < VexCount; i++)
			{
				//若不成边，或者已经访问过跳过
				if (curCol[i] == 0 || visited[i])
				{
					//当寻找到结尾发现栈内有元素，则出栈尝试在上一个位置寻找其他为被访问的点
					if (i == curCol.Length - 1 && stack.Count != 0)
					{
						var prePos = stack.Pop();
						curCol = Arcs[prePos];
						i = 0;
					}
					continue;
				}
				//记录访问位置
				Console.WriteLine(Vexs[i]);
				visited[i] = true;
				//入栈
				stack.Push(i);
				//重置位置
				curCol = Arcs[i];
				i = 0;
			}
		}


		//递归方式
		public void DFS2(int v, bool[] visited = null)
		{
			visited ??= new bool[VexCount];
			Console.WriteLine(Vexs[v]);
			//记录访问位置
			visited[v] = true;

			for (int w = 0; w < VexCount; w++)
				//有边存在，并且没有被访问
				if (Arcs[v][w] != 0 && visited[w] == false)
					DFS2(w, visited);

		}


		public void BFS(int start)
		{
			if (start < 0 || start > VexCount - 1)
			{
				throw new InvalidOperationException($"给定位置不合法");
			}

			//辅助数组
			var visited = new bool[Vexs.Length];
			//辅助队列
			var queue = new Queue<int>(VexCount);

			var curCol = Arcs[start];
			for (int i = 0; i < VexCount; i++)
			{
				if (curCol[i] == 0 && visited[i])
				{
					var pos = queue.Dequeue();
					curCol = Arcs[pos];
					i = 0;
					continue;
				}

				//入队
				queue.Enqueue(i);
				//访问+记录
				Console.WriteLine(Vexs[i]);
				visited[i] = true;
			}
		}




	}




	public void Test()
	{
		const int MAX = int.MaxValue;

		//构造无向图，有边记为1，特点:对称
		var g1 = new AMGraph(['A', 'B', 'C', 'D'], [
			[0,0,1,1],
			[0,0,1,0],
			[1,1,0,0],
			[1,0,0,0],
		]);

		//构造无向网,权值指定
		var g2 = new AMGraph(['A', 'B', 'C', 'D'], [
			[MAX,3,4,5],
			[3, MAX, MAX, MAX],
			[4, MAX, MAX, MAX],
			[5, MAX, MAX, MAX]
		]);

		//构造有向网,权值指定
		var g3 = new AMGraph(['A', 'B', 'C'], [
			[MAX,3,4,5],
			[MAX, MAX, MAX, MAX],
			[MAX, MAX, MAX, MAX],
			[MAX, MAX, MAX, MAX]
		]);


		//邻接矩阵好处
		//方便检查任意对顶点是否存在边
		//方便找任一顶点所有的【邻接点】（有边直接相连的点）

		//方便计算任意顶点的度
		//无向图，对应行（或列）非零元素个数
		//有向图：【对应行】非0元素的个数【出度】，【对应列】非0元素个数【入度】

		//缺点：
		//不便于增加删除节点
		//浪费空间--存稀疏图（点很多而边很少）有大量无效元素
		//---存储稠密图（特别是完全图）还是很合算的
		//浪费时间--统计稀疏图一共多少条边，时间复杂度O（n^2）
		//空间复杂度O（n^2）
	}

}
